package com.lsa.letcode.common;

import java.io.File;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;

import com.lsa.helpers.graph.AdjGraph;
import com.lsa.iview.trees.BinaryTree;
import com.lsa.iview.trees.BinaryTree.Node;
import com.lsa.iview.trees.BinaryTreeUtils;

public class TreeUtils {
	public static AdjGraph<String, String> toAdjGraph(TreeLinkNode n){
		AdjGraph<String, String> g = new AdjGraph<String, String>(true, 0);
		Map<TreeLinkNode, Integer> node2Number = new HashMap<>();
		addVertices(n, g, node2Number);
		addEdges(g, n, node2Number);
		return g;
	}
	
	public static void addEdges(AdjGraph<String, String> g, TreeLinkNode n, Map<TreeLinkNode, Integer> node2Number) {
		if (n != null){
			Map<TreeLinkNode, String> node2Attr = new HashMap<TreeLinkNode, String>();
			node2Attr.put(n.next, "N");
			node2Attr.put(n.left, "L");
			node2Attr.put(n.right, "R");
			for (TreeLinkNode t : Arrays.asList(n.next, n.left, n.right)) {
				if (t != null){
					g.addEdge(node2Number.get(n), node2Number.get(t), node2Attr.get(t));
				}
			}
			addEdges(g, n.left, node2Number);
			addEdges(g, n.right, node2Number);
		}
	}
	
	private static void addVertices(TreeLinkNode n, AdjGraph<String, String> g, Map<TreeLinkNode, Integer> node2Number) {
		if (n != null){
			addVertices(n.left, g, node2Number);
			node2Number.put(n, g.addNode(""+n.val));
			addVertices(n.right, g, node2Number);
		}
	}
	
	public static int nodeCount(TreeLinkNode n) {
		if (n == null){
			return 0;
		}
		else {
			return 1 + nodeCount(n.left) + nodeCount(n.right); 
		}
	}
	
	
	public static TreeNode fromTgf(Class<?> c, String resourceName) throws IOException {
		InputStream in = c.getResourceAsStream(resourceName);
		return TreeUtils.fromTgf(in);
	}
	
	public static TreeNode fromTgf(InputStream in) throws IOException {
		BinaryTree<Integer> fromTgf = BinaryTreeUtils.fromTgf(in);
		TreeNode r2 = adaptNode(fromTgf.getRoot());
		if (fromTgf.getRoot() != null){
			doCopyAdaptTree(fromTgf.getRoot(), r2);
		}
		return r2;
	}
	
	public static void toTgf(TreeNode n, File f) throws IOException {
		Node<Integer> t2 = copyAdaptTree(n);
		BinaryTreeUtils.writeAsTgfToFile(t2, f.getAbsolutePath());
	}
	
	public static void toTgf(TreeLinkNode n, File f) {
		
	}

	public static int maxDepthRec(TreeNode root) {
		if (root == null) {
			return 0;
		} else {
			return 1 + Math
					.max(maxDepthRec(root.left), maxDepthRec(root.right));
		}
	}
	
	public static boolean areEqual(TreeNode n1, TreeNode n2) {
		if (n1 == null){
			return n2 == null;
		}
		else if (n2 == null) {
			return false;
		}
		
		if (!areEqual(n1.left, n2.left)) {
			return false;
		}
		
		if (n1.val != n2.val) {
			return false;
		}
		
		return areEqual(n1.right, n2.right);
	}
	
	public static boolean areEqual(TreeNode r2, Node<Integer> r1) {
		return areEqual(r1, r2);
	}
	
	public static boolean areEqual(Node<Integer> r1, TreeNode r2) {
		if (r1 == null) {
			return r2 == null;
		}
		else if (r2 == null) {
			return false;
		}
		
		if (!areEqual(r1.getLeft(), r2.left)) {
			return false;
		}
		
		if (!Objects.equals(r1.getData(), r2.val)) {
			return false;
		}
		
		return areEqual(r1.getRight(), r2.right);
	}

	public static TreeNode copyAdaptTree(Node<Integer> r) {
		TreeNode res = adaptNode(r);
		doCopyAdaptTree(r, res);
		return res;
	}
	
	public static Node<Integer> copyAdaptTree(TreeNode r) {
		Node<Integer> res = adaptNode(r);
		doCopyAdaptTree(r, res);
		return res;
	}
	
	public static TreeLinkNode copyAdaptTree2TreeLinkNode(TreeNode r){
		TreeLinkNode res = adaptNode2TreeLinkNode(r);
		doCopyAdaptTree(r, res);
		return res;
	}
	
	public static List<Integer> preorder(TreeNode n){
    	List<Integer> l = new ArrayList<Integer>();
    	preorderRec(n, l);
    	return l;
    }
    
    private static void preorderRec(TreeNode n, List<Integer> l){
    	if (n != null) {
    		l.add(n.val);
    		preorderRec(n.left, l);
    		preorderRec(n.right, l);
    	}
    }
    
    public static List<Integer> inorder(TreeNode n){
    	List<Integer> l = new ArrayList<Integer>();
    	inorderRec(n, l);
    	return l;
    }
    
    private static void inorderRec(TreeNode n, List<Integer> l){
    	if (n != null) {
    		inorderRec(n.left, l);
    		l.add(n.val);
    		inorderRec(n.right, l);
    	}
    }
    
    public static List<Integer> postorder(TreeNode n){
    	List<Integer> l = new ArrayList<Integer>();
    	 postorderRec(n, l);
    	return l;
    }
    
    private static void postorderRec(TreeNode n, List<Integer> l){
    	if (n != null) {
    		postorderRec(n.left, l);
    		postorderRec(n.right, l);
    		l.add(n.val);
    	}
    }
	
	private static void doCopyAdaptTree(Node<Integer> r, TreeNode r2) {
		if (r.getLeft() != null) {
			r2.left = adaptNode(r.getLeft());
			doCopyAdaptTree(r.getLeft(), r2.left);
		}
		if (r.getRight() != null) {
			r2.right = adaptNode(r.getRight());
			doCopyAdaptTree(r.getRight(), r2.right);
		}
	}
	
	private static void doCopyAdaptTree(TreeNode r, TreeLinkNode r2) {
		if (r.left != null){
			r2.left = adaptNode2TreeLinkNode(r.left);
			doCopyAdaptTree(r.left, r2.left);
		}
		
		if (r.right != null) {
			r2.right = adaptNode2TreeLinkNode(r.right);
			doCopyAdaptTree(r.right, r2.right);
		}
	}
	
	private static void doCopyAdaptTree(TreeNode r, Node<Integer> r2) {
		if (r.left != null) {
			r2.setLeft(adaptNode(r.left));
			doCopyAdaptTree(r.left, r2.getLeft());
		}
		if (r.right != null) {
			r2.setRight(adaptNode(r.right));
			doCopyAdaptTree(r.right, r2.getRight());
		}
	}
	
	private static TreeNode adaptNode(Node<Integer> n) {
		if (n == null){
			return null;
		}
		return new TreeNode(n.getData());
	}
	
	private static Node<Integer> adaptNode(TreeNode n) {
		if (n == null){
			return null;
		}
		return new Node<Integer>(n.val);
	}
	
	private static TreeLinkNode adaptNode2TreeLinkNode(TreeNode n) {
		if (n == null){
			return null;
		}
		return new TreeLinkNode(n.val);
	}
}